package com.lsa.helpers;

import java.util.ArrayList;
import java.util.List;

public abstract class CollectionUtils
{
	public static Object[] toArray(List list, int from, int to)
	{
		Object[] array = new Object[to - from + 1];
		for (int i = from; i < to + 1; i++)
		{
			array[i - from] = list.get(i);
		}
		
		return array;
	}
	
	/**
	 * @param list
	 * @param pivotElIdx
	 * @return
	 * 
	 // division procedure
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );

	 */
	public static int pivotDivide(List<Integer> list, int left, int right, 
			int pivotElIdx)
	{
		Integer pivotEl = list.get(pivotElIdx);

		int i = left;
		int j = right;
		
		list.set(pivotElIdx, list.get(i));
		list.set(i, EMPTY);
		
		while(i < j)
		{
			//Case A. A[i] is empty and A[ j] ≤ pivot: A [ j ] belongs on the left, so move it to the
			//empty A [i]. Now A [ j ] is empty. Increase the left side by increasing i by one.

			if (list.get(i) == EMPTY && list.get(j) <=  pivotEl)
			{
				list.set(i, list.get(j));
				list.set(j, EMPTY);
				i++;
			}
			//Case B. A[i] is empty and A[ j] > pivot: A [ j ] belongs on the right and is already
			//there. Increase the right side by decreasing j by one.
			else if (list.get(i) == EMPTY && list.get(j) >  pivotEl)
			{
				j--;
			}
			//Case C. A[ j] is empty and A[i] ≤ pivot: A [i] belongs on the left and is already
			//there. Increase the left side by increasing i by one.
			else if (list.get(j) == EMPTY && list.get(i) <=  pivotEl)
			{
				i++;
			}
//			Case D. A[ j] is empty and A[i] > pivot: A [i] belongs on the right, so move it to
//			the empty A [ j ]. Now A [i] is empty. Increase the right side by decreasing j by one.
			else if (list.get(j) == EMPTY && list.get(i) >  pivotEl)
			{
				list.set(j, list.get(i));
				list.set(i, EMPTY);
				j--;
			}
			
		}
		
		list.set(i, pivotEl);
		return i;
	}
	
	private static int EMPTY = Integer.MIN_VALUE; 
	
	/*
	 * function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right − 1
         if array[i] ≤ pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex
*/
	
	public static List<Integer> mergeAsc(List<Integer> list1, List<Integer> list2)
	{
		List<Integer> listResult = new ArrayList<Integer>(list1.size() + list2.size());
		listResult.addAll(list1);
		listResult.addAll(list2);
		
		int i,j,k;
		i = j = k = 0;
		
		// IND: n = 2
		// n - 1
		// 
		
		while(i != list1.size() || j != list2.size())
		{
			if (i != list1.size() && j != list2.size())
			{
				if (list1.get(i) == list2.get(j))
				{
					listResult.set(k++, list1.get(i++));
					listResult.set(k++, list2.get(j++));
				}
			}
			
			if (i != list1.size() )
			{
				if (j == list2.size() || list1.get(i) < list2.get(j))
				{
					listResult.set(k++, list1.get(i++));
				}
			}
			
			// INV: i == list1.size() || list1.get(i) >= list2.get(j)
			
			if (j != list2.size() )
			{
				if (i == list1.size() || list2.get(j) < list1.get(i))
				{
					listResult.set(k++, list2.get(j++));
				}
			}
			
			// INV: j == list2.size() || list1.get(i) <= list2.get(j)
		}
		
		return listResult;
	}
}
